/* 0. 代码随想录 */
// step 0# 全局变量定义
char** result;          // 保存所有合法的IP字符串结果
int resultTop;          // 当前结果数量
int segments[3];        // 用于记录当前尝试在字符串中插入的三个点的位置

// step 1# 判断从 s[start] 到 s[end] 之间的字符串是否是合法的 IP 段
int isValid(char* s, int start, int end) {
    if (start > end) return 0;

    // step 1.1# 如果是多位数但以0开头，不合法
    if (s[start] == '0' && start != end) return 0;

    int num = 0;

    // step 1.2# 遍历字符串，累加转换成整数
    for (int i = start; i <= end; i++) {
        if (s[i] < '0' || s[i] > '9') return 0;  // 非数字字符
        num = num * 10 + (s[i] - '0');
        if (num > 255) return 0;                // 超过255不合法
    }

    return 1;  // 合法
}

// step 2# 回溯函数：startIndex为当前搜索起点，pointNum为已放置的点数量
void backTracking(char* s, int startIndex, int pointNum) {
    // step 2.1# 放置了3个点后，检查最后一段是否合法
    if (pointNum == 3) {
        if (isValid(s, startIndex, strlen(s) - 1)) {
            // step 2.1.1# 分配空间给当前合法的 IP 地址字符串
            char* tempString = (char*)malloc(sizeof(char) * (strlen(s) + 4)); // 多出三个点和一个 '\0'

            int count = 0;   // tempString 的下标
            int count1 = 0;  // 已放置的点数

            // step 2.1.2# 构造带点的 IP 地址字符串
            for (int j = 0; j < strlen(s); j++) {
                tempString[count++] = s[j];
                if (count1 < 3 && j == segments[count1]) {
                    tempString[count++] = '.';
                    count1++;
                }
            }
            tempString[count] = '\0'; // step 2.1.3# 字符串结尾

            // step 2.1.4# 将结果添加到 result 中（realloc 扩容）
            result = (char**)realloc(result, sizeof(char*) * (resultTop + 1));
            result[resultTop++] = tempString;
        }
        return;
    }

    // step 2.2# 从 startIndex 继续枚举下一段
    for (int i = startIndex; i < strlen(s); i++) {
        if (isValid(s, startIndex, i)) {
            // step 2.2.1# 当前段合法，记录点的位置
            segments[pointNum] = i;

            // step 2.2.2# 递归进入下一段
            backTracking(s, i + 1, pointNum + 1);
        } else {
            break; // step 2.2.3# 不合法则提前剪枝
        }
    }
}

// step 3# 主函数入口：恢复所有可能的 IP 地址组合
char ** restoreIpAddresses(char * s, int* returnSize){
    // step 3.1# 初始化结果数组
    result = (char**)malloc(0);
    resultTop = 0;

    // step 3.2# 启动回溯
    backTracking(s, 0, 0);

    // step 3.3# 返回结果
    *returnSize = resultTop;
    return result;
}


/* 1. 20250422 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

// step 0# 全局变量：结果数组和临时分隔点数组
char **ans;
int ansTop;
int point[3];

// step 1# 截取字符串 s[start:end]，生成一个新子串
char *cutString(char *s, int start, int end) {
    int len = end - start + 1;
    char *sub = (char *)malloc(sizeof(char) * (len + 1));
    for (int i = 0; i < len; i++) {
        sub[i] = s[start + i];
    }
    sub[len] = '\0';
    return sub;
}

// step 2# 判断某段字符串是否为合法 IP 字段
bool isValid(char *sub) {
    int len = strlen(sub);
    if (len == 0 || len > 3) return false;          // 长度限制（最大3位）
    if (len > 1 && sub[0] == '0') return false;     // 前导0非法（除0本身）
    int val = atoi(sub);
    return val >= 0 && val <= 255;                  // 数值范围合法性
}

// step 3# 构造完整 IP 地址并加入结果
void processIp(char *s, int len) {
    char *ip = (char *)malloc(sizeof(char) * (len + 4 + 1)); // 原长 + 3 个 '.' + '\0'
    int ipIndex = 0;
    int pointIndex = 0;

    for (int i = 0; i < len; i++) {
        ip[ipIndex++] = s[i];
        if (pointIndex < 3 && i == point[pointIndex]) {
            ip[ipIndex++] = '.';
            pointIndex++;
        }
    }

    ip[ipIndex] = '\0';
    ans[ansTop++] = ip;
}

// step 4# 回溯核心函数
void backtracking(char *s, int startIndex, int pointNum) {
    int len = strlen(s);

    // step 4.1# 若已经放置了3个点（即4段），检查最后一段是否合法
    if (pointNum == 3) {
        char *last = cutString(s, startIndex, len - 1);
        if (isValid(last)) {
            processIp(s, len);  // step 4.2# 拼接合法 IP
        }
        free(last);
        return;
    }

    // step 4.3# 枚举当前段（最多3位）
    for (int i = startIndex; i < len && i - startIndex < 3; i++) {
        char *sub = cutString(s, startIndex, i);
        if (isValid(sub)) {
            point[pointNum] = i;                      // step 4.3.1# 记录点位
            backtracking(s, i + 1, pointNum + 1);     // step 4.3.2# 回溯下一段
        } else {
            free(sub);
            break;  // step 4.3.3# 不合法则立即剪枝
        }
        free(sub);
    }
}

// step 5# 主函数：初始化 + 启动回溯
char** restoreIpAddresses(char* s, int* returnSize) {
    int len = strlen(s);
    ans = (char **)malloc(sizeof(char *) * 1000);
    ansTop = 0;

    // step 5.1# 提前剪枝：字符串长度必须在合法范围内
    if (len < 4 || len > 12) {
        *returnSize = 0;
        return NULL;
    }

    // step 5.2# 启动回溯
    backtracking(s, 0, 0);
    *returnSize = ansTop;
    return ans;
}
